﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Konves.Collections
{
    public sealed partial class IntervalDictionary<TBound, TValue>
    {
        [DebuggerDisplay("[{Interval.LowerBound},{Interval.UpperBound}]: {Value}")]
        // TODO: Add XML Documentation
        private class IntervalNode
        {
            public IntervalNode(IInterval<TBound> interval, TValue value, IntervalNode parent)
            {
                this.Interval = interval;
                this.Value = value;
                this.Parent = parent;
            }

            public IInterval<TBound> Interval { get; set; }

            public IntervalNode Left;
            public IntervalNode Right;
            public IntervalNode Parent;

            public int Height
            {
                get
                {
                    return this.GetHeight();
                }
            }

            public int BalanceFactor
            {
                get
                {
                    return this.GetBalanceFactor();
                }
            }

            public BalanceOperation BalanceOperation
            {
                get
                {
                    return this.GetBalanceOperation();
                }
            }

            public TValue Value { get; set; }

            public void Insert(IInterval<TBound> interval, TValue value)
            {
                if (this.Interval.Intersects(interval))
                    throw new ArgumentException("other", "other exists or intersects an existing interval");

                if (interval.CompareTo(this.Interval) < 0)
                {
                    if (this.Left == null)
                        this.Left = new IntervalNode(interval, value, this);
                    else
                        this.Left.Insert(interval, value);
                    IntervalNode.Balance(ref this.Left);
                }
                else
                {
                    if (this.Right == null)
                        this.Right = new IntervalNode(interval, value, this);
                    else
                        this.Right.Insert(interval, value);
                    IntervalNode.Balance(ref this.Right);
                }
            }

            public void Delete(IInterval<TBound> interval)
            {
                throw new NotImplementedException();
            }

            private int GetHeight()
            {
                return Math.Max(
                    this.Left == null ? 0 : this.Left.GetHeight() + 1,
                    this.Right == null ? 0 : this.Right.GetHeight() + 1
                    );
            }

            private int GetBalanceFactor()
            {
                return (this.Left == null ? -1 : this.Left.Height) - (this.Right == null ? -1 : this.Right.Height);
            }

            private BalanceOperation GetBalanceOperation()
            {
                if (this.BalanceFactor < -1)
                    if (this.Right.BalanceFactor < 0)
                        return BalanceOperation.RightRight;
                    else
                        return BalanceOperation.RightLeft;
                else if (this.BalanceFactor > 1)
                    if (this.Left.BalanceFactor < 0)
                        return BalanceOperation.LeftRight;
                    else
                        return BalanceOperation.LeftLeft;
                else
                    return BalanceOperation.None;
            }

            public bool IsLeaf
            {
                get
                {
                    return
                        this.Left == null
                        && this.Right == null;
                }
            }

            public bool IsRoot
            {
                get
                {
                    return this.Parent == null;
                }
            }

            [Obsolete]
            public TValue Find(TBound key)
            {
                TValue value;
                if (TryFind(key, out value))
                    return value;
                else
                    throw new KeyNotFoundException();
            }

            [Obsolete]
            public TValue Find(IInterval<TBound> interval)
            {
                TValue value;
                if (TryFind(interval, out value))
                    return value;
                else
                    throw new KeyNotFoundException();
            }

            public bool TryFind(TBound key, out TValue value)
            {
                if (Interval.Contains(key))
                {
                    value = Value;
                    return true;
                }
                else if (key.CompareTo(Interval.LowerBound) < 0)
                    if (Left == null)
                    {
                        value = default(TValue);
                        return false;
                    }
                    else
                        return Left.TryFind(key, out value);
                else
                    if (Right == null)
                    {
                        value = default(TValue);
                        return false;
                    }
                    else
                        return Right.TryFind(key, out value);
            }

            public bool TryFind(IInterval<TBound> interval, out TValue value)
            {
                if (Interval.Equals(interval))
                {
                    value = this.Value;
                    return true;
                }
                else if (interval.CompareTo(Interval) < 0)
                    if (Left == null)
                    {
                        value = default(TValue);
                        return false;
                    }
                    else
                        return Left.TryFind(interval, out value);
                else
                    if (Right == null)
                    {
                        value = default(TValue);
                        return false;
                    }
                    else
                        return Right.TryFind(interval, out value);
            }

            // TODO: Implement TrySetValue
            public void SetValue(TBound key, TValue value)
            {
                if (Interval.Contains(key))
                    this.Value = value;
                else if (key.CompareTo(Interval.LowerBound) < 0)
                    if (Left == null)
                        throw new KeyNotFoundException();
                    else
                        Left.SetValue(key, value);
                else
                    if (Right == null)
                        throw new KeyNotFoundException();
                    else
                        Right.SetValue(key, value);
            }

            // TODO: Implement TrySetValue
            public void SetValue(IInterval<TBound> interval, TValue value)
            {
                if (Interval.Equals(interval))
                    this.Value = value;
                else if (interval.CompareTo(Interval) < 0)
                    if (Left == null)
                        throw new KeyNotFoundException();
                    else
                        Left.SetValue(interval, value);
                else
                    if (Right == null)
                        throw new KeyNotFoundException();
                    else
                        Right.SetValue(interval, value);
            }

            public IEnumerable<IntervalValuePair<TBound, TValue>> Traverse()
            {
                if (this.Left != null)
                    foreach (var node in this.Left.Traverse())
                        yield return node;

                yield return new IntervalValuePair<TBound, TValue>(this.Interval, this.Value);

                if (this.Right != null)
                    foreach (var node in this.Right.Traverse())
                        yield return node;
            }

            public IEnumerable<IInterval<TBound>> GetIntervals()
            {
                if (this.Left != null)
                    foreach (var interval in this.Left.GetIntervals())
                        yield return interval;

                yield return this.Interval;

                if (this.Right != null)
                    foreach (var interval in this.Right.GetIntervals())
                        yield return interval;
            }

            public IEnumerable<TValue> GetValues()
            {
                if (this.Left != null)
                    foreach (var value in this.Left.GetValues())
                        yield return value;

                yield return this.Value;

                if (this.Right != null)
                    foreach (var value in this.Right.GetValues())
                        yield return value;
            }

            public bool ContainsKey(TBound key)
            {
                return
                    this.Interval.Contains(key)
                    || (this.Left != null && this.Left.ContainsKey(key))
                    || (this.Right != null && this.Right.ContainsKey(key));
            }

            public bool ContainsInterval(IInterval<TBound> interval)
            {
                return
                    this.Interval.Equals(interval)
                    || (this.Left != null && this.Left.ContainsInterval(interval))
                    || (this.Right != null && this.Right.ContainsInterval(interval));
            }

            public IntervalNode First()
            {
                if (this.Left == null)
                    return this;
                else
                    return this.Left.First();
            }

            public IntervalNode Last()
            {
                if (this.Right == null)
                    return this;
                else
                    return this.Right.Last();
            }
        
            public static void RotateLeft(ref IntervalNode root)
            {
                var rootParent = root.Parent;
                var pivot = root.Right;
                var temp = pivot.Left;

                pivot.Left = root;
                root.Parent = pivot;
                root.Right = temp;

                if (temp != null)
                    temp.Parent = root;
                if (pivot != null)
                    pivot.Parent = rootParent;

                root = pivot;
            }

            public static void RotateRight(ref IntervalNode root)
            {
                var rootParent = root.Parent;
                var pivot = root.Left;
                var temp = pivot.Right;

                pivot.Right = root;
                root.Parent = pivot;
                root.Left = temp;

                if (temp != null)
                    temp.Parent = root;
                if (pivot != null)
                    pivot.Parent = rootParent;

                root = pivot;
            }

            public static void Balance(ref IntervalNode root)
            {
                switch (root.BalanceOperation)
                {
                    case BalanceOperation.LeftLeft:
                        RotateRight(ref root);
                        break;
                    case BalanceOperation.LeftRight:
                        RotateLeft(ref root.Left);
                        RotateRight(ref root);
                        break;
                    case BalanceOperation.RightLeft:
                        RotateRight(ref root.Right);
                        RotateLeft(ref root);
                        break;
                    case BalanceOperation.RightRight:
                        RotateLeft(ref root);
                        break;
                }
            }

            public static void Delete(ref IntervalNode node)
            {
                if (node == null)
                    throw new ArgumentNullException();

                // Leaf
                if (node.IsLeaf)
                {
                    if (!node.IsRoot)
                        if (object.ReferenceEquals(node.Parent.Left, node))
                            node.Parent.Left = null;
                        else
                            node.Parent.Right = null;

                    node.Parent = null;
                }
                // Only Left subtree
                else if (node.Left != null && node.Right == null)
                {
                    if (!node.IsRoot)
                        if (object.ReferenceEquals(node.Parent.Left, node))
                            node.Parent.Left = node.Left;
                        else
                            node.Parent.Right = node.Left;

                    // TODO: bug!
                    node.Left.Parent = node.Parent;

                    node.Parent = null;
                    node.Left = null;

                }
                // Only Right subtree
                else if (node.Right != null && node.Left == null)
                {

                    if (!node.IsRoot)
                        if (object.ReferenceEquals(node.Parent.Left, node))
                            node.Parent.Left = node.Right;
                        else
                            node.Parent.Right = node.Right;

                    // TODO: bug!
                    node.Right.Parent = node.Parent;

                    node.Parent = null;
                    node.Right = null;
                }
                // Left and Right subtree
                else if (node.Left != null && node.Right != null)
                {

                }

            }
        }

        public enum BalanceOperation
        {
            None,
            LeftLeft,
            LeftRight,
            RightLeft,
            RightRight
        }
    }
}
